Recent studies have shown that the memory systems of large parallel computers can potentially suffer from a performance-crippling defect. If a significant fraction of memory references are addressed to one memory address, the performance of the whole system can be limited by the capacity of that one memory. If access to that memory is via a multistage interconnection network, a phenomenon known as "tree blockage" will result in additional contention, causing substantial delays to all users of that system.
This problem and related performance issues are discussed in an article, "Hot-Spot Contention and Combining in Multistage Interconnection Networks," specifically referenced in the subsequent "Prior Art" section.
One solution to this problem is a "combining network," as proposed in the NYU Ultracomputer design (see "The NYU Ultracomputer--Designing a MIMD, Shared Memory Parallel Machine," IEEE Transactions on Computers, February 1983, pp. 175-189). The combining network causes references to the memory Hot Spot to be combined enroute to memory, reducing the contention for the Hot Spot; however a combining network is a complex and expensive hardware design. It is currently difficult if not infeasible to build a combining network of sufficiently low latency to sustain all memory references in a large multiprocessor system. An alternative approach is to build two networks, one for low latency and one other capable of handling high contention traffic, and to divert those messages which are expected to cause Hot Spots into the second network. However, the problem remains of effectively selecting the Hot-Spot references from general memory traffic. It is of course possible to rely on software or some predesignation of message types in such a system to avoid the Hot-Spot problem by designating what references are to Hot Spots. Thus the Hot Spots are pre-identified. Such a solution, however, is clearly unworkable in a large multi-user system, because the performance of the whole system will be dependent on correct and efficient programming by all users with an implied inference of consistency in designating what type of references are Hot Spots.
Thus, while the concept of an interconnection network for such a multiprocessor multimemory module interconnection system has been proposed having a low-latency network and a potential high-latency Hot-Spot combining network has been proposed, no efficient means or mechanism is known for dynamically identifying those messages which are Hot Spots and for subsequently controlling the interconnection mechanism.